Adjacency Matrix: Another Representation Method for Graphs and a Comparison of Advantages and Disadvantages

An adjacency matrix is a fundamental representation of a graph, essentially an n×n two-dimensional array where rows and columns correspond to the vertices of the graph, and element values indicate the existence or weight of edges between vertices. In an undirected graph, the value 1 represents the presence of an edge, and 0 represents its absence; in a weighted graph, the actual weight value is directly stored. Its advantages include: first, checking the existence of an edge takes only O(1) time, and calculating vertex degrees is efficient (for undirected graphs, it is the sum of a row, while for directed graphs, rows and columns correspond to out-degrees and in-degrees respectively); second, it is suitable for dense graphs (with edge counts close to n²), has high space utilization, and is simple to implement, making it easy for beginners to understand. Disadvantages include: a space complexity of O(n²), which wastes significant space for sparse graphs; traversing adjacent vertices requires O(n) time, making it less efficient than adjacency lists; and insufficient flexibility for dynamically adjusting the number of edges. In summary, the adjacency matrix trades space for time. It is suitable for dense graphs or scenarios requiring frequent edge queries or degree calculations, but unsuitable for sparse graphs or scenarios requiring frequent traversal of adjacent vertices. It serves as a foundational tool for understanding graph structures.